package history.dynamicArray;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

/**
 * @author czt
 * @version 1.0
 * @since 2024/10/24
 *
 * 动态数组
 *
 * 如果二维数组要遍历，需要行作为外循环，列作为内循环，这样可以利用CPU和内存之间的缓存来提高效率(空间局部性)
 * 缓存行是缓存存储的最小单位，一般是64字节
 */
public class DynamicArray implements Iterable<Integer>{
    private int capacity = 8; //数组容量

    private int size = 0; //逻辑大小，用来控制数组中有效元素的个数

    private int[] array = {}; //初始为空数组，懒加载

    //向数组中有效元素的后一个索引位置插入元素
    public void addLast(int element) {
        //size此时就和 数组有效元素的后一个索引位置 相同
        array[size] = element;
        //添加完元素后size向后移一位
        size++;
    }

    //向数组中某个位置插入元素
    public void add(int index, int element) {
        //懒加载
        if (size == 0) {
            array = new int[capacity];
        }else if (size == capacity) {
            //扩容，容量检查，如果size(有效元素个数)等于数组容量，那么需要进行扩容(之前的1.5倍)
            capacity = capacity + capacity >> 1;

            int[] newArray = new int[capacity];

            System.arraycopy(array, 0, newArray, 0, size);

            //新数组取代就数组
            array = newArray;
        }

        // 1 2 3 4 5
        // 1 2 6 3 4 5
        // index为2，size为5
        // 向索引2的位置插入元素6；3，4，5均需要向后移动，就要使用数组的拷贝功能
        // 数组元素拷贝
        // 参数说明：从那个数组拷贝(源数组)，拷贝元素的起始索引，要拷贝到那个数组中去(目标数组)，新数组中起始元素的索引，拷贝元素的个数
        if (index >= 0 && index < size) {
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        // 之后为数组赋值
        array[index] = element;
        //添加完元素后size向后移一位
        size++;

    }

    //根据索引获取元素
    public int get(int index) {
        return array[index];
    }

    //遍历元素
    public void foreach(Consumer<Integer> consumer) {
        for (int i = 0; i < size; i++) {
            consumer.accept(array[i]);
        }
    }

    //遍历元素-迭代器
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;
            @Override
            public boolean hasNext() { //判断是否有下一个元素
                return i < size;
            }

            @Override
            public Integer next() { //返回当前元素，并指向下一个元素
                return array[i++]; //先返回当前元素，再++
            }
        };
    }

    public IntStream stream() {
        //这个拷贝方法含头不含尾，size又是有效元素的个数，正好比索引大一个
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }

    //删除方法
    public int remove(int index) {
        //后面的元素向前移一位
        if (index < size - 1) {
            System.arraycopy(array, index + 1, array, index, size - index - 1);
        }
        //同时size减小
        size--;
        return array[index];
    }
}
